package com.qfedu.entity.course06;

import lombok.Data;

/**
 * 自己实现二叉搜索树
 */
@Data
public class BSTree<E extends Comparable<E>> {

    /**
     * 根节点
     */
    private TreeNode<E> root;
    /**
     * 树的节点数量
     */
    private int size;

    /**
     * 查询容量
     */
    public int size() {
        return size;
    }


    /**
     * 是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 添加元素
     */
    public void add(E e) {
        root = add(root, e);
        size++;
    }

    private TreeNode<E> add(TreeNode<E> root, E e) {
        if (root != null) {
            if (e.compareTo(root.data) > 0) {
                root.right = add(root.right, e);
                root.right.parent = root;
            } else if (e.compareTo(root.data) < 0) {
                root.left = add(root.left, e);
                root.left.parent = root;
            }
            return root;
        } else {
            return new TreeNode<>(e);
        }
    }

    /**
     * 添加元素
     */
    public void addNoRecursion(E e) {
        //从根节点开始查找
        TreeNode<E> cur = root;
        //待插入节点的父节点
        TreeNode<E> parent = null;
        int cmp = 0;
        while (cur != null) {
            cmp = e.compareTo(cur.data);
            if (cmp > 0) {
                parent = cur;
                cur = cur.right;
            } else if (cmp < 0) {
                parent = cur;
                cur = cur.left;
            } else {
                return;
            }
        }
        TreeNode<E> node = new TreeNode<>(e);
        if (parent == null) {
            root = node;
        } else {
            if (cmp < 0) {
                parent.left = node;
            } else {
                parent.right = node;
            }
            node.parent = parent;
        }
        size++;
    }

    /**
     * 删除指定元素
     */
    public boolean remove(E e) {
        TreeNode<E> node = find(root, e);
        if (node == null) {
            return false;
        }
        fastRemove(node);
        size--;
        return true;
    }

    public TreeNode<E> find(E e) {
        return find(root, e);
    }

    /**
     * 在以root为根节点的树中查找值为e的节点
     */
    private TreeNode<E> find(TreeNode<E> root, E e) {
        if (root != null) {
            if (e.compareTo(root.data) > 0) {
                return find(root.right, e);
            } else if (e.compareTo(root.data) < 0) {
                return find(root.left, e);
            } else {
                return root;
            }
        }
        return null;
    }

    private void fastRemove(TreeNode<E> node) {
        //node为待删除的节点
        //将删除一个有左孩子和右孩子的节点的情况转换成删除没有左孩子或没有右孩子的情况
        //查找待删除节点的后继节点
        if (node.left != null && node.right != null) {
            //使用后继节点代替待删除节点
            TreeNode<E> successor = minimum(node.right);
            node.data = successor.data;
            node = successor;
        }
        TreeNode<E> replacement = (node.left != null) ? node.left : node.right;
        if (replacement != null) {
            replacement.parent = node.parent;
        }
        if (node.parent == null) {
            //待删除节点没有父节点
            root = replacement;
        } else {
            if (node == node.parent.left) {
                node.parent.left = replacement;
            } else {
                node.parent.right = replacement;
            }
        }
        node.left = node.right = node.parent = null;
    }

    private TreeNode<E> minimum(TreeNode<E> root) {
        TreeNode<E> cur = root;
        while (cur.left != null) {
            cur = cur.left;
        }
        return cur;
    }

    /**
     * 删除任意元素
     */
    public void removeWithoutParent(E e) {
        boolean success = fastRemoveWithoutParent(root, e);
        if (success) {
            size--;
        }
    }

    /**
     * 删除以node为根节点中值为e的节点
     *
     * @param node 根节点
     * @param e    待删除的值
     * @return 删除是否成功
     */
    private boolean fastRemoveWithoutParent(TreeNode<E> node, E e) {
        //待删除节点的父节点
        TreeNode<E> parent = null;
        TreeNode<E> cur = node;
        //查找到待删除的节点
        while (cur != null) {
            if (e.compareTo(cur.data) > 0) {
                parent = cur;
                cur = cur.right;
            } else if (e.compareTo(cur.data) < 0) {
                parent = cur;
                cur = cur.left;
            } else {
                break;
            }
        }
        //表示没有找到待删除节点
        if (cur == null) {
            return false;
        }
        //将删除一个有左孩子和右孩子的节点的情况转换成删除没有左孩子或没有右孩子的情况
        //查找待删除节点的后继节点
        if (cur.left != null && cur.right != null) {
            TreeNode<E> successor = cur.right;
            parent = cur;
            while (successor.left != null) {
                parent = successor;
                successor = successor.left;
            }
            //使用后继节点代替待删除节点
            cur.data = successor.data;
            cur = successor;
        }

        TreeNode<E> replacement = (cur.left != null) ? cur.left : cur.right;
        if (parent == null) {
            //待删除节点没有父节点
            root = replacement;
        } else {
            if (cur == parent.left) {
                parent.left = replacement;
            } else {
                parent.right = replacement;
            }
        }
        cur.left = cur.right = null;
        return true;
    }

    /**
     * 是否包含指定元素
     */
    public boolean contains(E e) {
        TreeNode<E> node = find(root, e);
        return node != null;
    }

    public static void main(String[] args) {
        BSTree<Integer> bst = new BSTree<>();
        int[] nums = {5, 3, 6, 8, 4, 2};
        for (int num : nums) {
            bst.add(num);
        }
        System.out.println(bst);
    }
}
